home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / listings / v_12_06 / gotwals / test3.cpp < prev    next >
C/C++ Source or Header  |  1994-04-01  |  957b  |  39 lines
  1. ====================== Listing 8 ======================
  2. /* test3.cpp
  3.    Lucas-Lehmer test for primality of 2^p - 1
  4.    If p > 2 is a prime, then 2^p - 1 is prime if
  5.    and only if L[p-2] = 0, where the sequence L[i]
  6.    is defined as follows: L[0] = 4,
  7.    L[i+1] = (L[i]^2 - 2) modulo (2^p - 1)
  8.    ----------------------------------------------- */
  9. #include <stdio.h>
  10. #include "largeint.h"
  11.  
  12. void pause();
  13. void timer(int f);
  14.  
  15. int main() {
  16.    int p, i;
  17.    LargeInt L, mod;
  18.  
  19.    printf("Enter a prime number: ");
  20.    scanf("%d", &p);
  21.    timer(0); // start timer
  22.    mod.powerTwo(p);
  23.    mod = mod - 1; // mod = 2^p - 1
  24.    L = 4;
  25.    for (i = 2; i <= p - 1; i++) {
  26.       if (i % 100 == 0)
  27.          printf("%4d\r", i);
  28.       L = (L * L - 2) % mod;
  29.    }
  30.    printf("\n2^%d - 1 is ", p);
  31.    if (L == zero)
  32.       printf("prime\n");
  33.    else
  34.       printf("not prime\n");
  35.    printf("and the calculation took "), timer(1);
  36.  
  37.    return 0;
  38. }
  39.